package classic150;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2023/12/4 9:53
 * @description <p>leetcode274-H指数-数组-中等题</p>
 */
public class No274 {
    public static void main(String[] args) {
        int[] citations = {2, 2};
        System.out.println(hIndex(citations));
    }

    /**
     * （1）对citations数组进行从大到小的排序，最大的引用次数是 max = citations[len - 1]，最小引用次数是 min = citations[0]
     * （2）如果存在h指数，说明起码存在 h个数值大于 h的数
     * （3）二分法：如果left = 0, right = len - 1, mid = (left + right) >> 1
     * （4）如果 nums[mid] >= mid，说明有mid个数据、它们的值都大于mid。
     *     那么将mid右移，left = mid， mid = (left + right) >> 1，重复上面操作
     *     如果 nums[mid] < mid，mid左移，right = mid，mid = (left + right) >> 1，重复上面操作
     *     直到 left < right
     *
     * @param citations
     * @return
     */
    public static int hIndex(int[] citations) {
        Arrays.sort(citations);
        List<Integer> list = Arrays.stream(citations).boxed().collect(Collectors.toList());
        Collections.reverse(list);

        int left = 0;
        int right = list.size() - 1;
        int mid = 0;

        // {6, 5, 3, 1, 0}
        // {3, 1, 1}
        // {2, 2}
        while (left < right){
            mid = (left + right + 1) >> 1;
            if (list.get(mid) >= mid){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }

        return mid;
    }
}